package array;

/**
 * 给你一个整数数组 nums 和一个 正整数 k 。
 * 请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。
 * 子数组是数组中的一个连续元素序列。
 * <p>
 * 示例 1：
 * 输入：nums = [1,3,2,3,3], k = 2
 * 输出：6
 * 解释：包含元素 3 至少 2 次的子数组为：[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 。
 * <p>
 * 示例 2：
 * 输入：nums = [1,4,2,1], k = 3
 * 输出：0
 * 解释：没有子数组包含元素 4 至少 3 次。
 *
 * @author Jisheng Huang
 * @version 20250429
 */
public class CountSubarrAtLeastKTime_2962 {
    /**
     * Sliding window technique
     *
     * @param nums the given integer arr
     * @param k    the given integer
     * @return the count that satisfies the condition
     */
    public static long countSubarrays(int[] nums, int k) {
        int max = 0;

        for (int i : nums) {
            max = Math.max(max, i);
        }

        long ans = 0;
        int count = 0;  // 窗口中最大元素的计数
        int left = 0;

        // Sliding window
        for (int right = 0; right < nums.length; ++right) {
            if (nums[right] == max) {
                ++count;
            }

            // 当 count >= k 时，缩小窗口直到 count < k
            while (count >= k && left <= right) {
                // 以 left 开头、包含至少 k 个最大元素的子数组数量
                ans += nums.length - right;

                if (nums[left] == max) {
                    --count;
                }

                ++left;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 3, 3};
        int k = 2;

        System.out.println(countSubarrays(nums, k));

        nums = new int[]{1, 4, 2, 1};
        k = 3;

        System.out.println(countSubarrays(nums, k));
    }
}
